package com.hc.programming.tree;

import java.util.Arrays;

/**
 * 给定一个二叉树，判断它是否是
 * 平衡二叉树: 任何一个节点，左右子树高度差 <= 1
 * <p>
 * 示例 1：
 * <a href="./二叉树的层序遍历-示例1.png">示例1</a>
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：true
 * 示例 2：
 * <a href="./平衡二叉树-示例2.png">示例2</a>
 * 输入：root = [1,2,2,3,3,null,null,4,4]
 * 输出：false
 * 示例 3：
 * 输入：root = []
 * 输出：true
 * <p>
 * 提示：
 * 树中的节点数在范围 [0, 5000] 内
 * -10^4 <= Node.val <= 10^4
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/14 17:38
 */
public class 平衡二叉树 {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{3, 9, 20, null, null, 15, 7};
        TreeNode tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=true,--" + isBalanced(tree));
        arr = new Integer[]{1, 2, 2, 3, 3, null, null, 4, 4};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=false,--" + isBalanced(tree));
        arr = new Integer[]{};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=true,--" + isBalanced(tree));
        arr = new Integer[]{2, 1, 3};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=true,--" + isBalanced(tree));
        arr = new Integer[]{1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, null, null, 5, 5};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=true,--" + isBalanced(tree));
    }

    static class Result {
        boolean isBalanced;
        int height;

        public Result(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    public static boolean isBalanced(TreeNode root) {
        // 逻辑错了，判断成：任何2个叶子节点的高度差<=1
//        height = -1;
//        return 递归(root, 1);

//        Result result = getHeightAndStatus(root);
//        return result.isBalanced;

        int height = getHeight(root);
        return height != -1;
    }

    /**
     * 返回高度（-1表示不平衡）
     */
    private static int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) return -1;
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 方案一：返回高度和状态
     */
    private static Result getHeightAndStatus(TreeNode root) {
        if (root == null) return new Result(true, 0);
        if (root.left == null && root.right == null) return new Result(true, 1);
        Result left = getHeightAndStatus(root.left);
        Result right = getHeightAndStatus(root.right);
        if (!left.isBalanced || !right.isBalanced) return new Result(false, 0);
        if (Math.abs(left.height - right.height) > 1) return new Result(false, 0);
        return new Result(true, Math.max(left.height, right.height) + 1);
    }

//    static int height = -1;
//    private static boolean 递归(TreeNode root, int level) {
//        if (root == null) return true;
//        if (root.left == null && root.right == null) {
//            if (height == -1) {
//                height = level;
//                return true;
//            }
//            return Math.abs(height - level) <= 1;
//        }
//        if (root.left == null && (root.right.left != null || root.right.right != null)) return false;
//        if (root.right == null && (root.left.left != null || root.left.right != null)) return false;
//        return 递归(root.left, level + 1) && 递归(root.right, level + 1);
//    }

}
